13 Turing Machine

Context

After the Industrial Revolution, machines were transforming society:

• Steam engines
  
• Looms
  
• Railways

Could you make machines think?

Mechanical Reasoning

Railways – Interlocking Systems

• Prevented conflicting routes from being set.
  
• Used levers, gears, and rods to physically lock points and signals.
  
• Mechanical logic: if route A is set, route B is blocked.

Jacquard Looms

• Used punched cards to control fabric patterns.
  
• Holes allowed rods to pass and lift threads; no hole = thread stays down.
  
• Cards were read sequentially and reused → programmable patterns.

Babbage and Lovelace (1830s)

Charles Babbage designed the Analytical Engine.
Ada Lovelace imagined it manipulating symbols, not just numbers — anticipating general-purpose computation.

• Babbage — Father of the Computer
  
• Lovelace — First Programer

Their ideas set the stage for Turing in 1936.

Video: Hard Limits of Computation

Turing Machine

A mathematical abstraction of Babbage’s Analytical Engine.
A minimal universal model:

• Minimal components
  
• Capable of performing any computation

Only the tape is infinite:
- Not bound by memory or speed limits
- Everything else is finite — not magic

Turing Machine

Predates electronics.
Can be imagined as:

• A person following instructions
  
• A funky steampunk machine

Turing Machine Components

• Tape
  
• Tape Head
  
• State Table

Tape

• Infinite
  
• Divided into cells
  
• Each cell holds a symbol from a finite alphabet

Tape Head

• Reads the symbol
  
• Writes a new symbol
  
• Moves left or right

State Table

The program is a set of states.
Each state:

• Reads from the tape
  
• Writes to the tape
  
• Moves the head
  
• Transitions to the next state

Turing Machine

Why It Matters

Because it is simple and universal with infinite memory

anything that can be computed algorithmically

can be done by a Turing machine.

Example: Increment Binary Number

Alphabet: 1, 0 and blank ' '

Input: a binary number surround by blanks

Output: a binary number

Algorithm:

1. start at the right most digit
2. if read = 1, write 0 and go to the next digit
3. if read = 0, or blank write 1 and halt

State Transition Table:

Example input: 10101011

Start state: right

Example: Increment Binary Number

State transition table as diagram

Example: Check Input Format

Check that every a is followed by b

Alphabet: a, b, X, Y, R, A and blank ' '

Input: a string

Output: A and R

Algorithm:

1. Each a is marked and triggers a search for a b.

2. Each b is marked only once per a.

3. If any unmatched a is found, it rejects with R

Example: Check Input Format

Example input: abaabb

State transition table as diagram

Alt text